Linked List Operations (Insertion, Deletion, Traversal)

Linked List একটি ডাটা স্ট্রাকচার যা আংশিকভাবে বা সম্পূর্ণরূপে লিন্কড নোড থেকে তৈরি। প্রতি নোডের মধ্যে একটি ডাটা এলিমেন্ট এবং পরবর্তী নোডের জন্য একটি রেফারেন্স থাকে। এটি অ্যারে থেকে আলাদা, কারণ এখানে ফিক্সড সাইজের ডাটা স্টোরেজ নেই এবং এটি dynamic memory allocation ব্যবহার করে। Linked List বিশেষত ডাটা ইনসার্ট এবং ডিলিট করার ক্ষেত্রে খুব কার্যকরী।

এই গাইডে, আমরা Linked List এর কিছু মৌলিক অপারেশন (যেমন Insertion, Deletion, এবং Traversal) জাভা দিয়ে কিভাবে বাস্তবায়ন করা যায় তা দেখব।

1. Linked List Definition

লিঙ্কড লিস্টের একটি সাধারণ গঠন হল:

• Node: একটি নোডের দুটি অংশ থাকে - data এবং next (যা পরবর্তী নোডের রেফারেন্স বা পয়েন্টার থাকে)।
• Head: লিঙ্কড লিস্টের প্রথম নোডটি head নামে পরিচিত। এটি লিস্টের সমস্ত অপারেশন পরিচালনার জন্য ব্যবহার করা হয়।

public class LinkedList {
    Node head;  // Head of the list

    // Linked List Node
    static class Node {
        int data;
        Node next;

        // Constructor
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
}

এখানে, Node ক্লাসের মধ্যে data এবং next রয়েছে। head হল লিঙ্কড লিস্টের প্রথম নোড।

2. Insertion in Linked List

Insertion হলো লিঙ্কড লিস্টের মধ্যে নতুন নোড যোগ করা। আমরা তিনটি মৌলিক ইনসারশন অপারেশন করতে পারিঃ

1. At the beginning (Start)
2. At the end (End)
3. At a specific position

2.1. Insertion at the Beginning

public void insertAtBeginning(int data) {
    Node newNode = new Node(data);
    newNode.next = head;  // Point the new node's next to current head
    head = newNode;  // Move head to point to the new node
}

এখানে, নতুন নোডটি প্রথমে ইনসার্ট করা হয় এবং head পয়েন্টারটি নতুন নোডের দিকে পরিবর্তিত হয়।

2.2. Insertion at the End

public void insertAtEnd(int data) {
    Node newNode = new Node(data);
    if (head == null) {
        head = newNode;  // If the list is empty, make the new node the head
        return;
    }
    Node last = head;
    while (last.next != null) {
        last = last.next;  // Traverse to the last node
    }
    last.next = newNode;  // Make the last node point to the new node
}

এখানে, আমরা লিস্টের শেষ নোডে পৌঁছানোর জন্য একটি লুপ ব্যবহার করি এবং তারপর নতুন নোডকে যুক্ত করি।

2.3. Insertion at a Specific Position

public void insertAtPosition(int data, int position) {
    if (position < 0) return;

    Node newNode = new Node(data);
    if (position == 0) {
        newNode.next = head;
        head = newNode;
        return;
    }

    Node current = head;
    for (int i = 0; current != null && i < position - 1; i++) {
        current = current.next;  // Traverse to the position before the desired position
    }

    if (current == null) {
        System.out.println("Position out of range.");
        return;
    }

    newNode.next = current.next;
    current.next = newNode;  // Insert the new node at the specified position
}

এখানে, নির্দিষ্ট পজিশনে ইনসার্ট করতে একটি লুপ ব্যবহার করা হয় এবং নতুন নোডটি যুক্ত করা হয়।

3. Deletion in Linked List

Deletion হলো লিঙ্কড লিস্ট থেকে একটি নোড মুছে ফেলা। আমরা তিনটি মৌলিক ডিলিশন অপারেশন করতে পারিঃ

1. At the beginning (Start)
2. At the end (End)
3. At a specific position

3.1. Deletion at the Beginning

public void deleteAtBeginning() {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }
    head = head.next;  // Move head to the next node
}

এখানে, head পয়েন্টারটি এক সেল সামনে সরানো হয়, যা আগের প্রথম নোডকে বাদ দেয়।

3.2. Deletion at the End

public void deleteAtEnd() {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }
    if (head.next == null) {
        head = null;  // If only one node exists, set head to null
        return;
    }

    Node secondLast = head;
    while (secondLast.next != null && secondLast.next.next != null) {
        secondLast = secondLast.next;  // Traverse to the second last node
    }
    secondLast.next = null;  // Remove the last node
}

এখানে, শেষ নোডটি বাদ দেওয়ার জন্য প্রথম থেকে শেষের দিকে একবার পুরো লিস্ট পার করে দ্বিতীয় শেষ নোডে পৌঁছানো হয় এবং তার পরবর্তী নোডকে null সেট করা হয়।

3.3. Deletion at a Specific Position

public void deleteAtPosition(int position) {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }

    if (position == 0) {
        head = head.next;  // Remove the head
        return;
    }

    Node current = head;
    for (int i = 0; current != null && i < position - 1; i++) {
        current = current.next;  // Traverse to the node just before the one to delete
    }

    if (current == null || current.next == null) {
        System.out.println("Position out of range.");
        return;
    }

    current.next = current.next.next;  // Remove the node at the specified position
}

এখানে, নির্দিষ্ট পজিশনে নোড মুছে ফেলা হয়। প্রথমে সঠিক পজিশনে পৌঁছানো হয় এবং তার পরবর্তী নোডকে current.next.next তে পয়েন্ট করা হয়।

4. Traversal in Linked List

Traversal হল লিঙ্কড লিস্টে সকল নোড দেখার একটি প্রক্রিয়া। এটি সাধারণত লিস্টের প্রথম নোড থেকে শুরু করে একে একে প্রতিটি নোডে পৌঁছানো হয়।

public void traverse() {
    if (head == null) {
        System.out.println("List is empty.");
        return;
    }
    Node current = head;
    while (current != null) {
        System.out.println(current.data);  // Print data of each node
        current = current.next;  // Move to the next node
    }
}

এখানে, head থেকে শুরু করে প্রতিটি নোডের ডাটা প্রিন্ট করা হয়, এবং পরবর্তী নোডে চলে যাওয়া হয় যতক্ষণ না লিস্টের শেষ নোডে পৌঁছানো হয়।

5. Complete Linked List Implementation Example

এখন, আমরা একটি সম্পূর্ণ Linked List ক্লাস দেখব, যা Insertion, Deletion, এবং Traversal অপারেশনগুলি অন্তর্ভুক্ত করবে।

public class LinkedList {
    Node head;  // Head of the list

    // Linked List Node
    static class Node {
        int data;
        Node next;

        // Constructor
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // Insert at the beginning
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Insert at the end
    public void insertAtEnd(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

    // Delete at the beginning
    public void deleteAtBeginning() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        head = head.next;
    }

    // Delete at the end
    public void deleteAtEnd() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        if (head.next == null) {
            head = null;
            return;
        }
        Node secondLast = head;
        while (secondLast.next != null && secondLast.next.next != null) {
            secondLast = secondLast.next;
        }
        secondLast.next = null;
    }

    // Traverse the list
    public void traverse() {
        if (head == null) {
            System.out.println("List is empty.");
            return;
        }
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.insertAtBeginning(10);
        list.insertAtBeginning(20);
        list.insertAtEnd(30);
        list.insertAtEnd(40);

        System.out.println("List after insertion:");
        list.traverse();  // Output: 20 -> 10 -> 30 -> 40 -> null

        list.deleteAtBeginning();
        System.out.println("List after deleting from beginning:");
        list.traverse();  // Output: 10 -> 30 -> 40 -> null

        list.deleteAtEnd();
        System.out.println("List after deleting from end:");
        list.traverse();  // Output: 10 -> 30 -> null
    }
}

এখানে, লিঙ্কড লিস্টের Insertion, Deletion, এবং Traversal অপারেশনগুলি একত্রিত করা হয়েছে। এটি একটি মৌলিক Linked List অ্যাপ্লিকেশন যা স্ট্যান্ডার্ড অপারেশনগুলো সিমুলেট করে।

সারাংশ

Linked List জাভাতে ডাটা স্ট্রাকচার হিসেবে খুবই কার্যকরী এবং এটি বিভিন্ন ধরনের Insertion, Deletion, এবং Traversal অপারেশনগুলির জন্য উপযুক্ত। এই গাইডে আমরা তিনটি প্রধান অপারেশন:

1. Insertion: লিঙ্কড লিস্টে নতুন নোড যোগ করা।
2. Deletion: লিঙ্কড লিস্ট থেকে নোড মুছে ফেলা।
3. Traversal: লিঙ্কড লিস্টের প্রতিটি নোড পরিদর্শন করা।

এগুলি বাস্তবায়ন করার মাধ্যমে, আপনি Linked List স্ট্রাকচারের সাথে কাজ করার মৌলিক ধারণা পাবেন এবং জাভাতে এর কার্যকরী ব্যবহার শিখবেন।